package com.mango.leet.code.hard;

/**
 * 84. 柱状图中最大的矩形
 */

import java.util.Stack;

/**
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 *  
 *
 * 示例 1:
 *
 *
 *
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 * 示例 2：
 *
 *
 *
 * 输入： heights = [2,4]
 * 输出： 4
 *  
 *
 * 提示：
 *
 * 1 <= heights.length <=105
 * 0 <= heights[i] <= 104
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LC84_LargestRectangleInHistogram {
    public static void main(String[] args) {
        //int[] heights = {2,1,5,6,2,3};
        //int[] heights = {2,4};
        //int[] heights = {9};
        int[] heights = {2,1,2};
        System.out.println(new Solution().largestRectangleArea(heights));
    }
    static class Solution {
        // 单调栈
        public int largestRectangleArea(int[] heights) {
            // 先将数组左右补零
            int[] newHeights = new int[heights.length+2];
            newHeights[0] = 0;
            for(int i=0;i<heights.length;i++){
                newHeights[i+1] = heights[i];
            }
            newHeights[heights.length+1] = 0;
            int max = 0;
            Stack<Integer> stack = new Stack();
            for(int i=0;i<newHeights.length;i++){
                // 如果当前高度小于栈顶，则计算面积
                while (!stack.isEmpty() && newHeights[i]<newHeights[stack.peek()]){
                    int cur = stack.pop();
                    // 高
                    int h = newHeights[cur];
                    // 右边界是当前下标 i
                    int right = i;
                    // 左边界是栈的上一个元素
                    int left = stack.peek();
                    int area = (right-left-1) * h;
                    if(area > max){
                        max = area;
                    }
                }
                stack.add(i);
            }
            return max;
        }
        // 暴力解法，超时 时间复杂度O(n2)
        public int largestRectangleArea2(int[] heights) {
            int n = heights.length;
            // 如果只有一个数，则直接返回
            if(n == 1){
                return heights[0];
            }
            // 双指针遍历，寻找最长的宽下最高的高
            int max = 0;
            for(int i=0;i<n;i++){
                int h = heights[i];
                if(h == 0){
                    continue;
                }
                for(int j=i;j<n;j++){
                    if(h > heights[j]){
                        h = heights[j];
                    }
                    int w = j-i+1;
                    int area = h * w;
                    if(max < area){
                        max = area;
                        System.out.println("area="+max+",h="+h+",w="+w);
                    }
                }
            }
            return max;
        }
    }
}
/**
 *  什么是单调栈
 * 单调栈就是栈里面存放的数据都是有序的，所以可以分为单调递增栈和单调递减栈两种。
 *
 * 单调递增栈就是从栈底到栈顶是从大到小
 * 单调递减栈就是从栈底到栈顶是从小到大
 */